The disclosed embodiments of the present invention relate to forwarding packets, and more particularly, to a scheduler and related method for deciding a final output queue by selecting one of multiple candidate output queues.
A network switch is a computer networking device that links different electronic devices. For example, the network switch receives an incoming packet generated from a source electronic device connected to it, and transmits an outgoing packet derived from the received packet to one or more destination electronic devices for which the received packet is meant to be received. In general, the network switch has a packet buffer for buffering packet data of packets received from ingress ports, and forwards the packets stored in the packet buffer through egress ports.
Concerning ingress packets to be forwarded through the same egress port, the ingress packets come from source electronic device connected to different ingress ports. Hence, the network switch may create a plurality of output queues for ingress packets received by different ingress ports, respectively. For example, each of the output queues corresponding to the same egress port may be simply built by storing packet identifiers (packet IDs) of packets to thereby record a packet linked list indicative of an output sequence of the packets actually stored in the packet buffer. Since there are multiple output queues, a scheduler is therefore needed to perform a plurality of scheduler operations each used for making one output queue decision that indicates which output queue is granted to output one packet to the egress port.
In general, the processing time required by a single scheduler operation should be shorter than a minimum packet transmission time (e.g., a transmission time of a 64-byte packet) to achieve the desired line rate. When the line rate becomes higher, the minimum packet transmission time is shorter accordingly. For example, when the network switch is used in a 10 Gigabit Ethernet (10 GbE) environment, the minimum packet transmission time may be 67.2 ns (nanosecond); when the network switch is used in a 40 Gigabit Ethernet (40 GbE) environment, the minimum packet transmission time may be 16.8 ns; and when the network switch is used in a 100 Gigabit Ethernet (100 GbE) environment, the minimum packet transmission time may be 6.72 ns. Hence, regarding a high-speed network application, how to design a network switch meeting the strict scheduler timing constraint is a challenge to designers in the pertinent field.